1. Field of the Invention
This invention relates to a device for executing modular arithmetic on multi-word (multiple-precision) integers and in particular to a device for executing two or more types of modular arithmetic.
2. Background Art
Many encryption systems use calculations performed on multi-word integers in a finite field. Here, a multi-word integer is an integer with a word-length exceeding that of the 32-bit word-length customarily used in a conventional CPU: for example 160 bits. If such a cryptosystem is to be implemented by a communication device or similar, an arithmetic unit capable of performing multi-word arithmetic at high-speed is required.
An arithmetic unit for performing encryption according to the RSA (Rivest, Shamir, Adleman) public-key cryptosystem is conventionally realized by manufacturing a specialized LSI formed from a multiplier and memory. Such an arithmetic unit is only capable of performing exponential modular arithmetic on multi-word integers. This computation is performed by repeatedly using a multiplier with a short bit-length. The arithmetic unit is used in combination with the CPU as a coprocessor.
One public key cryptosystem that has recently been gathering ground as an alternative to RSA encryption is elliptic curve cryptology (ECC). ECC is secure against attacks, such as index calculus, that are effective against RSA encryption, and uses key data with a much shorter word-length than that used in RSA encryption, while still preserving sufficiently high security. For example, the same level of security provided by a 1024-bit key in RSA encryption can be achieved in ECC with only a 160-bit key.
However, achieving such high security ECC requires a variety of other computations in addition to the exponential modular arithmetic necessary for RSA encryption. These include the four basic arithmetic operations, and computation performed using complex processing which is predetermined but includes conditional branches.
As a result, when ECC computation is performed using the above-mentioned specialized RSA encryption coprocessor, only a very limited number of calculations can be executed. In other words, most of the computation is performed by the CPU, so that overhead resulting from exchanges of control signals between the CPU and the coprocessor increases, thereby preventing high-speed processing from being realized.
On the other hand, if a software-based method in which the CPU executes all of the types of calculation necessary for ECC is used, the use of multi-word computation data requires the CPU to access the memory at an extremely high frequency. As a result, data cannot be supplied efficiently to the arithmetic unit in the CPU, preventing the realization of high-speed processing.